package syf.huffmantree;

import java.io.*;
import java.util.*;

public class ReviewHuffman {
    static Map<Byte,String> map=new HashMap<>();
    public static void main(String[] args) {

//        String s="i like like like java do you like a java";
//        byte[] origin=s.getBytes();
//        //将数组转换成List集合
//        List<HuffmanNode> list = rankHuffman(origin);
//        //将数组装入List集合，并生成赫夫曼树
//        HuffmanNode huffman = createHuffman(list);
//        //得到每个叶子节点的路径，即赫夫曼表
//        Map<Byte, String> huffmanTable = getHuffmanTable(huffman);
//        //将赫夫曼表转化为字节数组
//        byte[] huffmanBytes = getHuffmanBytes(origin, huffmanTable);
//        System.out.println(Arrays.toString(huffmanBytes));

        /* 注释掉字符串压缩和解压
        //封装好的赫夫曼压缩,传入待压缩的文件的字节数组
        byte[] bytes = huffmanZip(origin);
        System.out.println(Arrays.toString(bytes));
        //赫夫曼压缩后的解压
        byte[] deByte = deCodeHuffman(map, bytes);
        System.out.println(new String(deByte));
        */

        //文件的压缩
//        String src="src/test/java/syf/TestHuffman/out682.txt";
//        String dest="src/test/java/syf/TestHuffman/out682.zip";
//        zipFile(src,dest);
//        System.out.println("压缩成功！！");
        //文件的解压
        String src="src/test/java/syf/TestHuffman/out682.zip";
        String dest="src/test/java/syf/TestHuffman/out6823.txt";
        unzipFile(src,dest);
        System.out.println("解压成功");
    }
    /********************************************压缩*************************************************/
    //封装好了的赫夫曼压缩
    private static byte[] huffmanZip(byte[] origin){
        //将数组转换成List集合
        List<HuffmanNode> list = rankHuffman(origin);
        //将数组装入List集合，并生成赫夫曼树
        HuffmanNode huffman = createHuffman(list);
        //得到每个叶子节点的路径，即赫夫曼表
        Map<Byte, String> huffmanTable = getHuffmanTable(huffman);
        //将赫夫曼表转化为字节数组
        return getHuffmanBytes(origin, huffmanTable);
    }

    //先得到每个字符对应的出现次数
    private static List<HuffmanNode> rankHuffman(byte[] origin){
        Map<Byte,Integer> map=new HashMap<>();
        //封装每个字符出现的次数
        for (int i=0;i<origin.length;i++){
            if (map.get(origin[i])==null){
                map.put(origin[i],1);
            }else {
                map.put(origin[i],map.get(origin[i])+1);
            }
        }
        //存入List中
        List<HuffmanNode> list=new ArrayList<>();
        for (Map.Entry<Byte,Integer> tmp:map.entrySet()){
            list.add(new HuffmanNode(tmp.getKey(),tmp.getValue()));
        }
        return list;
    }
    //将List排序，并生成赫夫曼树
    private static HuffmanNode createHuffman(List<HuffmanNode> list){
        while (list.size()>1){
            Collections.sort(list);
            HuffmanNode leftNode=list.get(0);
            HuffmanNode rightNode=list.get(1);
            HuffmanNode parent=new HuffmanNode(null,leftNode.weight+rightNode.weight);
            //将得到的左右节点放在新的父节点下，并从原数组移除左右节点，放入父节点
            parent.left=leftNode;
            parent.right=rightNode;
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parent);
        }
        return list.get(0);
    }
    /**
     * @param huffmanNode 生成的赫夫曼树的根节点
     * @param code 定义准则，左边为0 右边为1
     * @param path 每个叶子节点的路径
     * @return 返回map集合，里面装有所有叶子节点和它对应的路径
     */
    //得到赫夫曼表
    private static void getHuffmanTable(HuffmanNode huffmanNode,String code,StringBuilder path){
        StringBuilder builder=new StringBuilder(path);
        builder.append(code);
        if (huffmanNode!=null){
            //等于空说明为非叶子节点需要递归寻找
            if (huffmanNode.data==null){
                getHuffmanTable(huffmanNode.left,"0",builder);
                getHuffmanTable(huffmanNode.right,"1",builder);
            }else {//叶子节点，找到了一个了,需放入
                map.put(huffmanNode.data,builder.toString());
            }
        }
    }
    //重载赫夫曼树表
    private static Map<Byte,String> getHuffmanTable(HuffmanNode huffmanNode){
        StringBuilder strBu=new StringBuilder();
        getHuffmanTable(huffmanNode,"",strBu);
        return map;
    }
    //将赫夫曼表转化为字节数组
    private static byte[] getHuffmanBytes(byte[] origin,Map<Byte,String> map){
        byte[] tmp;
        StringBuilder stringBuilder=new StringBuilder();
        //先将赫夫曼表拼接
        for (int i=0;i<origin.length;i++){
            stringBuilder.append(map.get(origin[i]));
        }
//        System.out.println(stringBuilder.toString());
        //算出字节总数
        int count=stringBuilder.length()%8;//除出来等于0代表为8的倍数，否则加1
        if (count==0){
            tmp=new byte[stringBuilder.length()/8];
        }else {
            tmp=new byte[stringBuilder.length()/8+1];
        }
        //将上面的字符stringBuilder拆分放进tmp中 每8个一组, （注意要将其转为2进制转换！！！）
        int index=0;//记录放了多少个字节了
        for (int i=0;i<stringBuilder.length();i+=8){
            if (i+8>stringBuilder.length()){//不够8位
                tmp[index]=(byte)Integer.parseInt(stringBuilder.substring(i),2);
            }else {
                tmp[index]=(byte)Integer.parseInt(stringBuilder.substring(i,i+8),2);
            }
            index++;
        }
        //以上完成后就将字符分割开，放进字节中了
        return tmp;
    }
    /**************************************************解压************************************************************/
    /**
     * 功能： 对赫夫曼压缩后的数据进行解压
     * @param originMap 数据和赫夫曼字符串的对应关系
     * @param huffZip 赫夫曼压缩后生成的数组
     * @return 返回原始（被压缩前的数组）
     */
    //对压缩的赫夫曼解码
    private static byte[] deCodeHuffman(Map<Byte,String> originMap,byte[] huffZip){
        //将原本的key value 转置为 value key
        Map<String,Byte> revMap=new HashMap<>();
        for (Map.Entry<Byte,String> t:originMap.entrySet()){
            revMap.put(t.getValue(),t.getKey());
        }
        StringBuilder all=new StringBuilder();
        //将赫夫曼数组转换成字符串拼接起来
        for (int i=0;i<huffZip.length;i++){
            //最后一次不用补位，是多少就是多少，其余的不足需要补高位
            //最后一次需要补位，因为当最后一位为例如 000时，不补位只有一个0 不正确
            all.append(bitToBitString(huffZip[i]));
        }
        //当下的字符串
        String tmp;
        //往后移动的距离
        int count;
        //从map中获取到的源字节
        Byte t;
        //源数组
        byte[] bytes;
        List<Byte> list=new ArrayList<>();
        boolean flag=false;
        for (int i=0;i<all.length();){
            count=1;
            while (true){
                if (all.length()-i>8){
                    tmp=all.substring(i,i+count);
                }else {//判断最后一个了,从后往前，找出来了就直接退出
                    tmp=all.substring(all.length()-count);
                    flag=true;
                }
                t=revMap.get(tmp);
                if (t==null){//如果为空说明里面没有对应的哈夫曼表
                    count++;
                }else {
                    //不为空说明找到了，添加进去，跳出此次while循环
                    list.add(t);
                    break;
                }
            }
            i+=count;
            if (flag)//如果为true跳出，则说明为最后一个，且已经找到。直接跳出循环
                break;
        }
        bytes=new byte[list.size()];
        for (int i=0;i< list.size();i++){
            bytes[i]=list.get(i);
        }
        return bytes;
    }
    /**
     * 功能：将二进制字节转成字符串
//     * @param flag 标志高位是否需要补位，如果为true则需要补位，如果是false则不补位
     * @param huff 传入的byte
     * @return 传入的byte的二进制字符串 （补码形式返回）
     */
    private static String bitToBitString(byte huff){
        int tmp=huff;
        //flag为true进行补位，或上就行
        tmp |=256;  //256 为 1_0000_0000 tmp与其或了之后，就能达到补位的效果
        String str=Integer.toBinaryString(tmp);
        //因为是取的int的补码，所以我们只需要后面8位，前面8位截取掉
        return str.substring(str.length() - 8);
    }
    /******************************************文件压缩****************************************************/
    /**
     *
     * @param srcFile 要进行压缩的文件路径
     * @param destFile 压缩后文件放置的位置
     */
    private static void zipFile(String srcFile,String destFile){
        //创建缓冲流
        BufferedInputStream bi=null;
        BufferedOutputStream bo=null;
        //对象流，可按照写入顺序读出。一个为文件字节，一个为存储规则map
        ObjectOutputStream oos=null;
        //读取字节的数组
        byte[] getBytes;
        try {
            //将源文件的流读进来
            bi=new BufferedInputStream(new FileInputStream(srcFile));
            //获取源文件的字节大小，进行数组创建
            getBytes=new byte[bi.available()];
            //将文件读进getBytes
            bi.read(getBytes);
            //对文件进行压缩,得到赫夫曼压缩后数组
            byte[] huffmanBytes = huffmanZip(getBytes);
            //创建输出缓冲流
            bo=new BufferedOutputStream(new FileOutputStream(destFile));
            //使用对象流输出，方便按对象直接读取
            oos=new ObjectOutputStream(bo);
            oos.writeObject(huffmanBytes);
            oos.flush();
            oos.writeObject(map);
            oos.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            if (oos!=null) {
                try {
                    oos.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (bo!=null){
                try {
                    bo.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (bi!=null) {
                try {
                    bi.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    /******************************************文件解压****************************************************/
    /**
     *
     * @param srcFile 要进行解压的文件路径
     * @param destFile 解压后文件放置的位置
     */
    private static void unzipFile(String srcFile,String destFile){
        //创建缓冲流
        BufferedInputStream bi=null;
        BufferedOutputStream bo=null;
        //对象流，可按照写入顺序读出。一个为文件字节，一个为存储规则map
        ObjectInputStream ois=null;
        //读取字节的数组
        byte[] huffmanBytes;
        //压缩规则
        Map<Byte,String> zipRule;
        try {
            //将待解压的文件读进来
            bi=new BufferedInputStream(new FileInputStream(srcFile));
            //读成对象流，可以对象写出
            ois=new ObjectInputStream(bi);
            //写出压缩后的赫夫曼表，,按写入顺序读出
            huffmanBytes=(byte[]) ois.readObject();
            //写出压缩规则
            zipRule= (Map<Byte,String>)ois.readObject();
            //解压,得到原始字节
            byte[] bytes = deCodeHuffman(zipRule, huffmanBytes);
            //定义解压位置开始输出文件
            bo=new BufferedOutputStream(new FileOutputStream(destFile));
            bo.write(bytes);
            bo.flush();
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        } finally {
            if (ois!=null) {
                try {
                    ois.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (bo!=null){
                try {
                    bo.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if (bi!=null) {
                try {
                    bi.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}
class HuffmanNode implements Comparable<HuffmanNode>{
    HuffmanNode left;
    HuffmanNode right;
    int weight;
    Byte data;

    public HuffmanNode(Byte data,int weight) {
        this.weight = weight;
        this.data = data;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "data=" + data +
                ",weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(HuffmanNode o) {
        return this.weight-o.weight;
    }
}